package com.mystudy.algorithm.sort;

import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * @program: infoalgorithm
 * @description: 希尔排序
 * @author: zhouzhilong
 * @create: 2019-07-30 15:30
 **/
public class ShellSort {
    /**
     * logger
     */
    private static final Logger LOGGER = LoggerFactory.getLogger(ShellSort.class);

    @Test
    public void test() {
        int[] arr = new int[]{4, 1, 9, 5, 1, 9, 5, 6, 6, 9, 2, 15, 21, 96, 34};
        int[] sort = sort(arr);
        LOGGER.debug("sort = [{}]", sort);
    }


    private int[] sort(int[] arr) {
        int gap = arr.length / 2;//gap不仅是组数,还是步长
        while (gap > 0) {
            for (int i = gap; i < arr.length; i++) {
                int temp = arr[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && arr[preIndex] > temp) {
                    arr[preIndex + gap] = arr[preIndex];
                    preIndex -= gap;
                }
                arr[preIndex + gap] = temp;

            }
            gap = gap / 2;
        }
        return arr;

    }
}
